class MinHeap {
  constructor(data) {
    this.data = data || []
    this.compare = (a, b) => a - b
    this.heapify()
  }
  size() {
    return this.data.length
  }
  peek() {
    if (this.size() === 0) return null
    return this.data[0]
  }
  offer(v) {
    this.data.push(v)
    this.bubbleUp(this.size() - 1)
  }
  poll() {
    if (this.size() === 0) return null
    const result = this.data[0]
    const last = this.data.pop()
    if (this.size() !== 0) {
      this.data[0] = last
      this.bubbleDown(0)
    }
    return result
  }
  swap(index1, index2) {
    ;[this.data[index1], this.data[index2]] = [
      this.data[index2],
      this.data[index1],
    ]
  }
  heapify() {
    if (this.size() < 2) return
    for (let i = 1; i < this.size(); i++) {
      this.bubbleUp(i)
    }
  }
  bubbleUp(i) {
    while (i > 0) {
      const pIndex = (i - 1) >> 1
      if (this.compare(this.data[i], this.data[pIndex]) < 0) {
        this.swap(i, pIndex)
        i = pIndex
      } else {
        break
      }
    }
  }
  bubbleDown(i) {
    const lastIndex = this.size() - 1
    while (true) {
      const leftIndex = i * 2 + 1
      const rightIndex = i * 2 + 2
      let findIndex = i
      if (
        leftIndex <= lastIndex &&
        this.compare(this.data[leftIndex], this.data[findIndex]) < 0
      ) {
        findIndex = leftIndex
      }
      if (
        rightIndex <= lastIndex &&
        this.compare(this.data[rightIndex], this.data[findIndex]) < 0
      ) {
        findIndex = rightIndex
      }
      if (i !== findIndex) {
        this.swap(i, findIndex)
        i = findIndex
      } else {
        break
      }
    }
  }
}
